﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0103_MinStack : IAlgorithm
    {
        // 217. 存在重复元素

        // 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
        // push(x) —— 将元素 x 推入栈中。
        // pop() —— 删除栈顶的元素。
        // top() —— 获取栈顶元素。
        // getMin() —— 检索栈中的最小元素。

        // 提示：
        //  pop、top 和 getMin 操作总是在 非空栈 上调用。


        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            var obj = new MinStack();
            obj.Push(1);
            obj.Pop();
            Console.WriteLine(obj.Top());
            Console.WriteLine(obj.GetMin());
        }

        // 算法
        public class MinStack
        {
            class ListNode
            {
                public int val;
                public int min;//最小值
                public ListNode next;

                public ListNode(int val, int min, ListNode next)
                {
                    this.val = val;
                    this.min = min;
                    this.next = next;
                }
            }

            private ListNode stack = null;

            public MinStack()
            {

            }

            public void Push(int val)
            {
                var min = stack == null ? val : Math.Min(val, stack.min);
                stack = new ListNode(val, min, stack);
            }

            public void Pop()
            {
                stack = stack.next;
            }

            public int Top()
            {
                return stack.val;
            }

            public int GetMin()
            {
                return stack.min;
            }
        }
    }
}
